package algorithm.dynamic;

/**
 * @author Jonny Long
 * @date 2021/3/12 9:48
 */
public class DynamicTest {
    public static void main(String[] args) {
        //int[] A=new int[]{2,5,7};
        //int M=27;
        //System.out.println(DynamicTest.coinChange(A, M));
        //System.out.println(DynamicTest.uniquePaths(3, 3));
        int[] arr=new int[]{2,3,1,1,4};
        System.out.println(DynamicTest.canJump(arr));
    }

    /**
     * 动态规划，硬币问题
     * f[X]=min{f[X-2]+1,f[X-5]+1,f[X-7]+1}
     *
     * @param A 硬币金额种类
     * @param M 要凑够的总金额
     * @return 最少硬币
     */
    public static int coinChange(int[] A, int M) {
        int[] f = new int[M + 1];
        f[0] = 0;
        for (int i = 1; i <= M; i++) {
            f[i] = Integer.MAX_VALUE;
            for (int value : A) {
                //第一个条件是防止数组越界；第二个条件是防止MAX_VALUE+1溢出
                if (i >= value && f[i - value] != Integer.MAX_VALUE) {
                    f[i] = Math.min(f[i], f[i - value] + 1);
                }
            }
        }
        if (f[M] == Integer.MAX_VALUE) {
            f[M] = -1;
        }
        return f[M];
    }

    /**
     * 动态规划，机器人宫格问题
     *
     * @param m 行
     * @param n 列
     * @return 多少种走法
     */
    public static int uniquePaths(int m, int n) {
        int[][] f = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    f[i][j] = 1;
                } else {
                    f[i][j] = f[i - 1][j] + f[i][j - 1];
                }
            }
        }
        return f[m - 1][n - 1];
    }

    /**
     * 跳石头问题
     * @param A 每个位置能跳的距离
     * @return 是否能跳成功
     */
    public static boolean canJump(int[] A){
        boolean[] f = new boolean[A.length];
        f[0]=true;
        for (int i = 1; i < A.length; i++) {
            f[i]=false;
            for (int j = 0; j < i; j++) {
                if (f[j] && j + A[j] >= i) {
                    f[i] = true;
                    break;
                }
            }
        }
        return f[A.length - 1];
    }
}
